This paper presents a proof of correctness of an iterative approximateByzantine consensus (IABC) algorithm for directed graphs. The iterativealgorithm allows fault- free nodes to reach approximate conensus despite thepresence of up to f Byzantine faults. Necessary conditions on the underlyingnetwork graph for the existence of a correct IABC algorithm were shown in ourrecent work [15, 16]. [15] also analyzed a specific IABC algorithm and showedthat it performs correctly in any network graph that satisfies the necessarycondition, proving that the necessary condition is also sufficient. In thispaper, we present an alternate proof of correctness of the IABC algorithm,using a familiar technique based on transition matrices [9, 3, 17, 19]. The key contribution of this paper is to exploit the following observation:for a given evolution of the state vector corresponding to the state of thefault-free nodes, many alternate state transition matrices may be chosen tomodel that evolution cor- rectly. For a given state evolution, we identify oneapproach to suitably "design" the transition matrices so that the standardtools for proving convergence can be applied to the Byzantine fault-tolerantalgorithm as well. In particular, the transition matrix for each iteration isdesigned such that each row of the matrix contains a large enough number ofelements that are bounded away from 0.
展开▼
